package com.wjy.Data_Structure.tree;

import com.wjy.Data_Structure.linearlist.common.Iterator;
import com.wjy.Data_Structure.linearlist.common.LinkedList;
import com.wjy.Data_Structure.linearlist.listslinkimpl.LinkedListDLNode;
import com.wjy.Data_Structure.queue.Queue;
import com.wjy.Data_Structure.queue.QueueArray;
import com.wjy.Data_Structure.stack.Stack;
import com.wjy.Data_Structure.stack.StackSLinked;
import com.wjy.Data_Structure.strategy.DefaultStrategy;
import com.wjy.Data_Structure.strategy.Strategy;

public class BinaryTreeLinked implements BinTree {
	protected BinTreeNode root;
	protected Strategy strategy;

	public BinaryTreeLinked() {
		this(null);
	}

	public BinaryTreeLinked(BinTreeNode root) {
		this(root, new DefaultStrategy());
	}

	public BinaryTreeLinked(BinTreeNode root, Strategy strategy) {
		this.root = root;
		this.strategy = strategy;
	}

	@Override
	public int getSize() {
		return root == null ? 0 : root.getSize();
	}

	@Override
	public boolean isEmpty() {
		return root == null;
	}

	@Override
	public BinTreeNode getRoot() {
		return root;
	}

	@Override
	public int getHeight() {
		return isEmpty() ? -1 : root.getHeight();
	}

	/**
	 * 递归查找元素
	 * @return
	 */
	private BinTreeNode searchE(BinTreeNode rt, Object e) {
		if (rt == null)
			return null;
		if (strategy.equal(rt.getData(), e))
			return rt; //如果是根结点，返回根
		BinTreeNode v = searchE(rt.getLChild(), e); //否则在左子树中找
		if (v == null)
			v = searchE(rt.getRChild(), e); //没找到，在右子树中找
		return v;
	}

	@Override
	public BinTreeNode find(Object e) {
		return searchE(root, e);
	}

	@Override
	public Iterator preOrder() {
		LinkedList list = new LinkedListDLNode();
		preOrderRecursion(this.root, list);
		return list.elements();
	}

	/**
	 * 先序遍历的递归算法 
	 * @param rt
	 * @param list
	 */
	private void preOrderRecursion(BinTreeNode rt, LinkedList list) {
		if (rt == null)//递归基,空树直接返回 
			return;
		list.insertLast(rt); //访问根结点 
		preOrderRecursion(rt.getLChild(), list);//遍历左子树 
		preOrderRecursion(rt.getRChild(), list);//遍历右子树
	}

	/**
	 * 先序遍历的非递归算法 
	 * @param rt
	 * @param list
	 */
	private void preOrderTraverse(BinTreeNode rt, LinkedList list) {
		if (rt == null)
			return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while (p != null) {
			while (p != null) { //向左走到尽头 
				list.insertLast(p);// 访问根
				if (p.hasRChild())
					s.push(p.getRChild());
				p.getLChild();
			}
			if (!s.isEmpty())
				p = (BinTreeNode) s.pop(); //右子树根退栈遍历右子树 
		}
	}

	@Override
	public Iterator inOrder() {
		LinkedList list = new LinkedListDLNode();
		inOrderRecursion(this.root, list);
		return list.elements();
	}

	/**
	 * 中序遍历递归算法
	 * @param rt
	 * @param list
	 */
	private void inOrderRecursion(BinTreeNode rt, LinkedList list) {
		if (rt == null)//递归基,空树直接返回
			return;
		inOrderRecursion(rt.getLChild(), list);//遍历左子树
		list.insertLast(rt); //访问根结点
		inOrderRecursion(rt.getRChild(), list);//遍历右子树

	}

	/**
	 * 中序遍历的非递归算法
	 * @param rt
	 * @param list
	 */
	private void inOrderTraverse(BinTreeNode rt, LinkedList list) {
		if (rt == null)
			return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while (p != null || !s.isEmpty()) {
			while (p != null) {//一直向左走
				s.push(p); //将根结点入栈
				p = p.getLChild();
			}
			if (!s.isEmpty()) {
				p = (BinTreeNode) s.pop();//取出栈顶根结点访问之
				list.insertLast(p);
				p = p.getRChild(); //转向根的右子树进行遍历
			}
		}
	}

	@Override
	public Iterator postOrder() {
		LinkedList list = new LinkedListDLNode();
		postOrderRecursion(this.root, list);
		return list.elements();
	}

	/**
	 * 后序遍历递归算法
	 * @param rt
	 * @param list
	 */
	private void postOrderRecursion(BinTreeNode rt, LinkedList list) {
		if (rt == null)
			return;
		postOrderRecursion(rt.getLChild(), list);
		postOrderRecursion(rt.getRChild(), list);
		list.insertLast(rt);

	}

	/**
	 * 后序遍历非递归算法
	 * @param rt
	 * @param list
	 */
	private void postOrderTraverse(BinTreeNode rt, LinkedList list) {
		if (rt == null)
			return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while (p != null || !s.isEmpty()) {
			while (p != null) { //先左后右不断深入
				s.push(p); //将根节点入栈
				if (p.hasLChild())
					p = p.getLChild();
				else
					p = p.getRChild();

			}
			if (!s.isEmpty()) {
				p = (BinTreeNode) s.pop(); //取出栈顶根结点访问。
				list.insertLast(p);
			}
			//转向栈顶根结点的右子树继续后序遍历
			while (!s.isEmpty() && ((BinTreeNode) s.peek()).getRChild() == p) {
				p = (BinTreeNode) s.pop();
				list.insertLast(p);
			}
			//转向栈顶根结点的右子树继续后序遍历
			if (!s.isEmpty())
				p = ((BinTreeNode) s.peek()).getRChild();
			else
				p = null;
		}
	}

	@Override
	public Iterator levelOrder() {
		LinkedList list = new LinkedListDLNode();
		levelOrderTraverse(this.root, list);
		return list.elements();
	}

	/**
	 * 使用队列完成二叉树的按层遍历  从上到下、从 左到右按层进行
	 * @param root2
	 * @param list
	 */
	private void levelOrderTraverse(BinTreeNode rt, LinkedList list) {
		if (rt == null)
			return;
		Queue q = new QueueArray();
		q.enqueue(rt);
		while (!q.isEmpty()) {
			BinTreeNode p = (BinTreeNode) q.dequeue(); //取出队首结点p并访问之
			list.insertLast(p);
			if (p.hasLChild())
				q.enqueue(p.getLChild());
			if (p.hasRChild())
				q.enqueue(p.getRChild());
		}
	}

}
